package algotithm.weekendrace.biweeklycontest44.test2;

/**
 * @author zhouyanxiang
 * @Date 2021-01-2021/1/23-20:21
 */
public class Solution {

    public static void main(String[] args) {
        int[]encoded = {6,5,4,6};
        Solution solution = new Solution();
        int[] decode = solution.decode(encoded);
        for (int i = 0; i < decode.length; i++) {
            System.out.print(decode[i] + " ");
        }
    }

    public int[] decode(int[] encoded) {
        int n = encoded.length+1;
        int[] perm = new int[n];
        int res = 0;
        // perm所有元素的异或和,即前n个正整数所有的异或和
        for (int i = 1; i <= n; i++) {
            res ^= i;
        }
        // 再与perm中除了第一项的其余项的异或和，这样可以求出第一项perm[0]
        for (int i = 1; i < n-1; i+=2) {
            res ^= encoded[i];
        }
        perm[0] = res;
        for (int i = 0; i < n-1; i++) {
            perm[i+1] = encoded[i] ^ perm[i];
        }
        return perm;
    }
}
